-
Algorithme d'Euclide
Lemme AE
Soit \(a\geq b\). On veut calculer \(pgcd(a,b)\).
On effectue: \(a=bq+r_1\) er le Lemme AE \(\implies\) \(pgcd(a,b)=pgcd(b,r_1)\)
- Si \(r_1=0\), alors \(pgcd(a,b)=pgcd(b,0)=b\)
- Si \(r_1\gt 0\), on effectue \(b=r_1q_2+r_2\)
\(0\leq r_2\lt r_1\)
Lemme AE\(\implies\) \(pgcd(a,b)=pgcd(b,r_1)=pgcd(r_1,r_2)\)
On continue:
\(r_{k-1}=r_k.q_{k+1}+0\implies pgcd(a,b)=r_k\)
Et comme la suite \((r_k)_k\) est une suite géométrique strictement décroissante d'entiers \(\geq 0\), l'algorithme va s'arreter en un nombre fini d'étape.
